package interview.i_001_algorithm;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.Setter;

import java.util.HashMap;
import java.util.Map;

/**
 * 版本号比较
 * 进制转换，可以处理字符串在各种位置的情况，且区分大小写
 */
public class T005_VersionCompare {
    public static void main(String[] args) throws Exception {
        System.out.println(compareVersion(".1R23.0.01.0.0.", "0.01R23.0000.1."));
    }

    /**
     * 前者大则返回一个正数，后者大返回一个负数，相等则返回 0
     */
    static int compareVersion(String version1, String version2) {
        if (version1 == null || version2 == null) {
            return 0;
        }

        int p1 = 0, p2 = 0; // 双指针
        int n1 = version1.length(), n2 = version2.length();

        Pair<Integer, Long> pair;
        long v1, v2;
        while (p1 < n1 || p2 < n2) { // 两个指针都走完才跳出循环
            pair = getNextChar(version1, n1, p1);
            p1 = pair.getKey();
            v1 = pair.getValue();

            pair = getNextChar(version2, n2, p2);
            p2 = pair.getKey();
            v2 = pair.getValue();

            if (v1 != v2) {
                return v1 > v2 ? 1 : -1;
            }
        }

        return 0;
    }

    static Pair<Integer, Long> getNextChar(String version, int n, int p) {
        if (p > n - 1) { // 补全短的版本号
            return new Pair<>(p, 0L);
        }

        int index = p; // 从 p 开始，找下一个分隔符之间的字符串，用于进制转换比较大小
        while (index < n && version.charAt(index) != '.') {
            index++;
        }

        // index + 1 下一次跳过 .，substring 包前不包后(忽略掉 .)
        return new Pair<>(index + 1, conversion(version.substring(p, index)));
    }

    @Getter
    @Setter
    @AllArgsConstructor
    static class Pair<K, V> {
        private final K key;
        private final V value;
    }

    /**
     * 62 进制中的符号
     */
    static final char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a',
            'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
            't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K',
            'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};

    static long conversion(String num) { // 62 进制转 10 进制
        int base = digits.length;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < base; i++) {
            map.put(digits[i], i);
        }

        long result = 0;
        int length = num.length() - 1;
        for (int i = length; i >= 0; i--) {
            char c = num.charAt(i);
            Integer integer = map.get(c);
            result += integer * Math.pow(base, length - i);
        }
        return result;
    }
}
